
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Farzon Lotfi
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>LCC 3403 HashMaps Group</title>
<meta name="description" content="Guides to HashMaps" />
<meta name="keywords" content="Hashmaps, tutorials, lectures" />
<meta name="author" content="Farzon, Lotfi" />

<link href="style.css" rel="stylesheet" type="text/css" />

 <script>
    function load()
    {
      document.getElementById('wrap').style.display = 'none';
      document.getElementById('example').style.display = 'none';
      document.getElementById('example2').style.display = 'none';
      document.getElementById('example3').style.display = 'none';
      document.getElementById('example4').style.display = 'none';
      document.getElementById('example5').style.display = 'none';
      document.getElementById('example6').style.display = 'none';
      document.getElementById('example7').style.display = 'none';
    }
</script>

</head>
<script language="javascript" type="text/javascript">
function showHide(shID) {
  if (document.getElementById(shID)) {
    if (document.getElementById(shID+'-show').style.display != 'none') {
      document.getElementById(shID+'-show').style.display = 'none';
      document.getElementById(shID).style.display = 'block';
    }
    else {
      document.getElementById(shID+'-show').style.display = 'inline';
      document.getElementById(shID).style.display = 'none';
    }
  }
}
</script>
<body onload="load()">
<div class="wrapper row1">
  <header id="header" class="clear">
    <hgroup>
      <h1><a href="index.html">HashMaps</a></h1>
      <h2>The Refresher Course</h2>
    </hgroup>
    <nav>
      <ul>
        <li><a href="notes.html">Notes</a></li>
        <li><a href="videos.html">Web Series</a></li>
        <li><a href="demo.html">Demo</a></li>
        <li><a href="questions.html">Interview Questions</a></li>
        <li class="last"><a href="tips.html">Interview Tips</a></li>
      </ul>
    </nav>
  </header>
</div>
<!-- content -->
<div class="wrapper row2">
  <div id="container" class="clear">
    <!-- Slider -->
    <section id="slider" class="clear">
      <figure> <iframe src="https://docs.google.com/presentation/embed?id=1E6781InFQpuAGsp5p7HfDK-c4WsoWq_a1lfYN1d9iHw&start=false&loop=false&delayms=3000" frameborder="0" width="600" height="300" allowfullscreen="true" mozallowfullscreen="true" webkitallowfullscreen="true"></iframe>
      <figcaption>
          <h2> Interview Questions</h2>
           <p> To generate questions asked during interviews click "Show Questions" below.</p>
           <footer class="more0"><a href="#" id="wrap-show" class="showLink" onclick="showHide('wrap');return false;">Show Questions &raquo;</a></footer>
        </figcaption>
      </figure>
    </section>
    
    <div id="wrap" class="more">
    <h1>Interview Questions</h1>
    
    <p>Q1: What is a disadvantage of using hash tables?<a href="#" id="example-show" class="showLink" onclick="showHide('example');return false;">See Answer.</a></p>
    <div id="example" class="more">
      <p>A: They usually have wasted space, depending on the load factor. A high load factor leads to less wasted space but has more collisions in general.</p>
      <p><a href="#" id="example-hide" class="hideLink" onclick="showHide('example');return false;">Hide this content.</a></p>
    </div>
    
    
    <p>Q2: What are advantages of using hash tables?<a href="#" id="example2-show" class="showLink" onclick="showHide('example2');return false;">See Answer.</a></p>
    <div id="example2" class="more">
      <p>A: O(1) look-up, insertion, and deletion.</p>
      <p><a href="#" id="example2-hide" class="hideLink" onclick="showHide('example2');return false;">Hide this content.</a></p>
    </div>
    
    <p>Q3: What must hold true for any given hashing function?<a href="#" id="example3-show" class="showLink" onclick="showHide('example3');return false;">See Answer.</a></p>
    <div id="example3" class="more">
      <p>A: A key must always return the same hash value.</p>
      <p><a href="#" id="example3-hide" class="hideLink" onclick="showHide('example3');return false;">Hide this content.</a></p>
    </div>
    
     <p>Q4: When resizing a hash table, what is a standard way of doing this? In other words, what size should you make the new backend array?<a href="#" id="example4-show" class="showLink" onclick="showHide('example4');return false;">See Answer.</a></p>
    <div id="example4" class="more">
      <p>A: Generally, you double the current size of the backend array and add one to it in order to create what is known as a pseudo-prime.</p>
      <p><a href="#" id="example4-hide" class="hideLink" onclick="showHide('example4');return false;">Hide this content.</a></p>
    </div>
    
    <p>Q5: What does a compression function do?<a href="#" id="example5-show" class="showLink" onclick="showHide('example5');return false;">See Answer.</a></p>
    <div id="example5" class="more">
      <p>A: It takes the hash value of a key and mods it by the table size in order to make it fit into an accepted range of integers.</p>
      <p><a href="#" id="example5-hide" class="hideLink" onclick="showHide('example5');return false;">Hide this content.</a></p>
    </div>
    
    <p>Q6: What is the absolute worst case runtime for insertion, look-up, and deletion given a bad hash function?<a href="#" id="example6-show" class="showLink" onclick="showHide('example6');return false;">See Answer.</a></p>
    <div id="example6" class="more">
      <p>A: O(n)</p>
      <p><a href="#" id="example6-hide" class="hideLink" onclick="showHide('example6');return false;">Hide this content.</a></p>
    </div>
    
    <p>Q7: Suppose we have two linked lists that merge at some point. How could you find which node the lists merge at? What is the runtime efficiency of your solution?<a href="#" id="example7-show" class="showLink" onclick="showHide('example7');return false;">See Answer.</a></p>
    <div id="example7" class="more">
      <p>A: Use a hash map and iterate over one of the lists, inserting each node into the hash map. Then begin doing the same thing with the other list. Once you have a collision, you know you have hit a node that has already been added to the hash map, and thus have found where the two lists merge. This gives an O(n) runtime.</p>
      <p><a href="#" id="example7-hide" class="hideLink" onclick="showHide('example7');return false;">Hide this content.</a></p>
    </div>
    
    <p><a href="#" id="wrap-hide" class="hideLink" onclick="showHide('wrap');return false;">Hide Questions.</a></p>
  </div>
    

</div>
<!-- Footer -->
<div class="wrapper row3">
  <footer id="footer" class="clear">
    <p class="fl_left">Copyright &copy; 2012 - All Rights Reserved </p>
  </footer>
</div>
 <script type="application/dart" src="web/start.dart"></script>
 <script src="https://dart.googlecode.com/svn/branches/bleeding_edge/dart/client/dart.js"></script>
</body>

</html>
